#include <iostream>
#include "Sort.h"
#include <vector>
#include <string>
#include "UniformRandom.h"
#include<ctime>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <stdlib.h>


using namespace std;

void checkSort( const vector<int> & a )
{
    for( int i = 0; i < a.size( ); ++i )
        if( a[ i ] != i )
            cout << "Error at " << i << endl;
    cout << "Finished checksort" << endl;
}


template <typename AnyType>
void permute( vector<AnyType> & a )
{
    static UniformRandom r;

    for( int j = 1; j < a.size( ); ++j )
        swap( a[ j ], a[ r.nextInt( 0, j ) ] );
}

int main( )
{
    cout<<"99%乱序测试结果："<<endl;
    const int n1 = 19800;    //乱序个数
    const int n2 = 200;    //顺序个数
    time_t begin,end;
    double ret;
    vector<int> a( n1 );        
    vector<int> b( n2 );
    vector<int> c(n1+n2);
    for( int i = 1; i < a.size( ); ++i )  
        a[ i ] = a[ i - 1 ] + 1;
    for( int i = 0; i < b.size( ); ++i )
            b[i]=i + n1;
    for( int theSeed = 0; theSeed < 5; ++theSeed )
    {
        permute(a);
        for ( int i = 0; i < a.size( ); ++i )
            c[i]=a[i];
        for ( int i = 0; i < b.size( ); ++i )
            c[i + n1]=b[i];

        begin=clock();
        heapsort(c);
        end=clock();
        ret=double(end-begin)/CLOCKS_PER_SEC*1000;
        checkSort(c);
        cout<<"heapsort 第"<<theSeed + 1<<"次测试："<<ret<<"ms"<<endl;

        for ( int i = 0; i < a.size( ); ++i )
            c[i]=a[i];
        for ( int i = 0; i < b.size( ); ++i )
            c[i + n1]=b[i];

        begin=clock();
        quicksort(c);
        end=clock();
        ret=double(end-begin)/CLOCKS_PER_SEC*1000;
        checkSort( c );
        cout<<"quicksort 第"<<theSeed + 1<<"次测试："<<ret<<"ms"<<endl;

    
    }
    return 0;
};